Not Applicable
All of the material in this patent document is subject to copyright protection under the copyright laws of the United States and of other countries. The owner of the copyright has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the United States Patent and Trademark Office file or records, but otherwise reserves all copyright rights whatsoever.
1. Field of the Invention
This invention pertains generally to failure analysis methods applied to electronic circuitry, and more particularly to a method for diagnosing bridging faults in integrated circuits.
2. Description of the Background Art
Ensuring the high quality of integrated circuits (IC) is important for many reasons, including high production yield, confidence in fault-free circuit operation, and the reliability of delivered parts. Rigorous testing of circuits can prevent the shipment of defective parts, but improving the production quality of a circuit depends upon effective failure analysis; that is, the process of determining the cause of detected failures. Discovering the cause of failures in a circuit can often lead to improvements in circuit design or manufacturing processes, with the subsequent production of higher-quality integrated circuits.
Failure analysis usually comprises two tasks: fault diagnosis, which is a logical search to determine the likely sources of error, using circuit information and details about how the circuit failed; and fault location or defect identification, which is a physical search to discover the mechanism of failure in the actual defective part. Given the enormous number of circuit elements in modem ICs, and the number of layers in most complex circuits, physical searches cannot succeed without considerable guidance from fault diagnosis. If the diagnosis is either inaccurate or imprecise (identifying either incorrect or excessively many fault candidates, respectively), the process of fault location will consume, and possibly waste, considerable amounts of time and effort.
Bridging faults, which are defined as the unintentional electrical shorting of two gate outputs, are believed to be a common defect type in integrated circuits and their diagnosis is considered to be crucial in IC manufacturing. A circuit with n nodes has   "AutoLeftMatch"      (                            n                                      2                      )  
possible bridging faults; explicit consideration of all such faults in infeasible. Therefore, a need exists for a fast, accurate and computationally non-complex method for precise diagnosis of bridging faults, particularly with respect to combinational CMOS circuits and full-scan sequential circuits, in which all state elements are controllable and observable. Prior to the present invention, that need has not been met by the conventional diagnostics discussed below.
Fault diagnosis is the logical component of failure analysis; appropriately, its domain is that of the logical fault, or simply fault, which is an abstract representation of how an element in a defective circuit misbehaves. A description of the behavior and assumptions about the nature of a logical fault is referred to as a fault model.
As with testing, diagnosis traditionally involves the choice of a fault model; the most popular fault model for both testing and diagnosis is the single stuck-at fault model, in which a node in the circuit is assumed to be unable to change its logic value. The stuck-at model is popular due to its simplicity, and because it has proven to be effective both in providing test coverage and diagnosing a limited range of faulty behaviors. However, other fault models can be used in diagnosis, and will as be discussed.
The concepts of fault and fault model are separate from that of a defect, which usually refers to the physical mechanism, such as an electrical short or open, that produces the incorrect behavior of the circuit. A logical fault description is an abstract means of representing a defect, an aspect of defect behavior, a class of defects, or several classes of defects. For example, a stuck-at fault is commonly thought to represent the defect of a circuit node being shorted to either power or ground.
While it is common (and convenient) to speak of diagnosis as identifying or locating faults in a circuit, the underlying target of diagnosis is ultimately a physical defect; the fault models used are simply useful abstractions in the eventual identification of a defect or defect location. As will be discussed in the following sections, the association of diagnostic fault model to targeted defect is not inviolable: a diagnosis may be performed using one fault model while targeting a defect more accurately represented by another fault model.
The traditional method of fault diagnosis, referred to as cause-effect analysis, has been described as test-based fault localization; that is, identification of a defect location by comparing failures observed on a tester with those predicted in fault simulation. A fault simulator will describe the behavior of a circuit in the presence of a particular instance of a modeled fault, usually in the form of a fault signature. A fault signature is the complete list of all input patterns (or test vectors) and circuit outputs by which a fault is detected. Note; however, that term fault signature is often reserved for only the response of faulty circuits under test. For example, the term fault signature has been defined in the art as the characteristic function of the erroneous response produced by a fault without regard to fault type. In the description herein, however, as in much of common usage, the term signature is applied to actual behaviors, as well as simulated and abstract faults, such as in stuck-at signature and composite signature, which will be introduced later.
The process of test-based fault localization, then, is one of comparing the observed faulty behavior of the circuit with a set of fault signatures, each representing a fault candidate. The resulting set of matches, if any, constitutes a diagnosis.
Many early diagnostic systems used a simple matching process, in which the signature of a fault candidate would either have to match exactly the circuit""s fault signature, containing every error-carrying vector and output, or would have to be a subset thereof. As diagnostic techniques matured, the matching process became more flexible; a good example of a simple generalization is known as the partial-intersection operation that ranks matches by the size of intersection. Matching algorithms employed by diagnostic techniques are often essential in translating from abstract fault models to defects, or from targeted fault models to untargeted faults, or to handle the vagaries of faulty circuit behavior.
The following sections describe previous approaches taken to the problem of fault diagnosis. As indicated above, most traditional (cause-effect) techniques involve two primary elements: a fault model, and a comparison or matching algorithm. The approaches described are primarily organized by the fault model used: stuck-at, bridging, or another model. Each technique is presented with a description of the matching algorithm used for diagnosis construction. Subsequent sections discuss other techniques that are not as easily categorized by fault model and matching algorithm.
2.1 Stuck-at Fault Diagnosis
Early fault diagnosis systems targeted only stuck-at faults; the fault candidates were stuck-at nodes, and the candidates were described by stuck-at fault signatures. In addition, the actual defect mechanism was interpreted strictly as a single stuck-at circuit node; other defect types could not necessarily be precisely diagnosed.
Many early systems of VLSI diagnosis, such as Western Electric Company""s DORA and an early approach of Teradyne, Inc., attempted to incorporate the concept of test-based fault localization with the previous-generation method of diagnosis, called guided-probe analysis. Guided-probe analysis employed a physical voltage probe and feedback from an analysis algorithm to intelligently select accessible circuit nodes for evaluation. The Teradyne and DORA techniques attempted to supplement the guided-probe analysis algorithm with information from stuck-at signatures.
Both systems used relatively advanced (for their time) matching algorithms. The DORA system used a nearness calculation referred to as fuzzy match. The Teradyne system employed the concept of prediction penalties where the signature of a candidate fault is considered a prediction of some faulty behavior, made up of  less than output:vector greater than  pairs. When matching with the actual observed behavior, the Teradyne algorithm scored a candidate fault by penalizing for each  less than output:vector greater than  pair found in the stuck-at signature but not found in the observed behavior, and penalizing for each  less than output:vector greater than  pair found in the observed behavior but not the stuck-at signature. These have commonly become known as misprediction and non-prediction penalties, respectively. A related Teradyne system introduced the processing of possible-detects, or outputs in stuck-at signatures that have unknown logic values, into the matching process.
A system that uses a more sophisticated algorithm of parameterized matching has recently been presented by De and Gunda; in this system, the user can specify the relative importance of misprediction and non-prediction. A quantitative ranking is assigned to each stuck-at fault, from which some indication can be made about the existence of multiple stuck-at faults. In this way, the system can explicitly target defects that behave similar to the stuck-at model, including some opens, and multiple distinguishable stuck-at defects; it can also implicitly diagnose less-distinguishable multi-node defects, such as bridging faults, but with less expected success.
The example systems described above characterize the general trend of stuck-at model diagnosis, from simple to complex matching algorithms. It has become evident that most failures in CMOS circuits do not behave exactly like single stuck-at faults. The inclusion of increasingly more-complicated algorithms is the necessary result of the reliance of these systems on the overly-simple single stuck-at fault model.
2.2 Bridging Fault Diagnosis
Much of the attention in diagnosing modern circuits has turned from the stuck-at model to the bridging fault model, motivated by the common occurrence of shorted nodes. The majority of spot defects in modem CMOS technologies cause changes in the circuit description that result in electrical shorts, which implies that many failures can be modeled by bridging faults. To address this, several approaches have been taken towards incorporating the bridging fault model into traditional test-based fault localization.
The first steps towards bridging fault diagnosis retained the legacy of stuck-at signatures, using these readily-available fault descriptions to approximate or identify bridging fault behavior. Many simple approaches merely compared stuck-at signatures to the observed behavior, and implicated the (single) nodes which most closely matched. One approach, however, proved to be fairly interesting. That approach, referred to as MMA, was developed by Millman, McCluskey, and Acken. In MMA, pseudo-signatures for bridging faults are constructed from stuck-at signatures for the bridged nodes and a simple subset matching algorithm is employed. A more conventional application of stuck-at signatures, paired with a sophisticated matching algorithm, was developed by Chakravarty and Gong. However, both of those methods suffer from imprecision; the average diagnoses for both are very large, consisting of hundreds or thousands of candidates.
Diagnosing bridging faults with available single stuck-at fault information is an appealing idea, but such an approach can lead to unusably large diagnoses or an unacceptable percentage of misleading diagnoses, in which neither node involved in the actual short is identified by the fault candidates. To address those deficiencies, Aitken and Maxwell built dictionaries comprised of realistic faults. That approach is truly cause-effect analysis using the bridging fault-model; that is, the fault candidates are the same faults targeted for diagnosis. The method provides both excellent accuracy and precision; there are very few misleading diagnoses, and the resulting diagnoses are very small (less than 10 candidates).
While there are obvious advantages to diagnosing bridging faults with available single stuck-at faulting information, there are significant costs. The number of realistic faults in a circuit is significantly larger than the number of single stuck-at faults for a circuit; also, the cost of simulating each individual realistic fault is frequently much greater, requiring much more detailed knowledge of the circuit for model construction. In addition, actual bridging fault behavior often diverges from simulated behavior, requiring validation and refinement of the models. The continued search for a method of diagnosing bridging faults using inexpensive stuck-at signatures is driven by the cost and complexity of realistic fault models; the present invention presents such an approach, yielding similar results to the realistic fault model approach, but at a much lower cost.
A completely different approach is taken by methods referred to as IDDQ diagnosis. In IDDQ diagnosis, an otherwise static circuit is monitored for excessive current flow, which would indicate a fault-induced path from power to ground. Fault signatures can be constructed for IDDQ measurement; errors are detected at a single output, the point of current measurement. Normal test-based fault localization can then proceed, matching expected failures to observed failures. In addition, voltage (logical) measurements can be taken at the outputs, and conventional fault signatures used to refine the diagnosis. The advantages of IDDQ diagnosis are that the IDDQ signatures are easy to construct, and the resulting diagnoses are usually both precise and accurate. The disadvantages are that not all circuits are IDDQ testable; in addition, a large number of chips fail all IDDQ patterns applied.
2.3 Other Approaches
Several approaches to fault diagnosis are not neatly categorized by the combination of fault model and algorithm specification used above. Some have attempted to eliminate or minimize fault simulation, instead relying on such information as the propagation and sensitization cones of individual faults or fault-free circuit nodes. The approaches suggested by Abramovici and Breuer and Rajski and Cox are examples, and are referred to as effect-cause analysis. Both attempt to identify all fault-free lines, and so can implicitly diagnose multiple faults and various fault types, although the resulting diagnoses are often pessimistic and imprecise.
A technique that incorporates elements of both test-based fault localization and effect-cause analysis has been presented by Waicukauski and Lindbloom. The technique relies on a great deal of information: in addition to propagation and sensitization path information, it requires knowledge of internal-node logic values to eliminate candidate nodes. Stuck-at fault simulation is performed, but only for a reduced set of fault candidates. While the presented theory assumes stuck-at behavior for individual faulty nodes on a per-vector basis, it also allows for complex fault behaviors: specifically multiple-site faults. While this technique offers a great deal of flexibility in targeting faults, its computational cost and diagnostic precision are matters of concern.
2.4 Inductive Fault Analysis
The techniques described above do not use physical layout information to diagnose faults. Intuitively, however, identifying a fault as the cause of a defect has much to do with the relative likelihood of certain defects occurring in the actual circuit. Inductive Fault Analysis (IFA) uses the circuit layout to determine the relative probabilities of individual physical faults in the fabricated circuit.
Inductive fault analysis uses the concept of a spot defect (or point defect), which is an area of extra or missing conducting material that creates an unintentional electrical short or break in a circuit. As these spot defects often result in bridge or open behaviors, inductive fault analysis can provide a fault diagnosis of sorts: an ordered list of physical faults (bridges or opens) that are likely to occur, in which the order is defined by the relative probability of each associated fault. The relative probability of a fault is expressed as its weighted critical area (WCA), defined as the physical area of the layout that is sensitive to the introduction of a spot defect, multiplied by the defect density for that defect type. For example, two circuit nodes that run close to one another for a relatively long distance provide a large area for the introduction of a shorting point defect; the resulting large WCA value indicates that a bridging fault between these nodes is considered relatively likely.
Inductive fault analysis can alternatively be applied to diagnosis for the creation of fault lists. Inductive fault analysis tools such as Carafe can provide a realistic fault list, important for fault models such as the bridging fault model, in which the number of possible faults is intractable for most circuits. By limiting the candidates to only faults that can realistically occur in the fabricated circuit, a diagnosis can be obtained that is much more precise than one that results from consideration of all theoretical faults.
2.5 The MMA Algorithm
As indicated above, MMA suffers from computational complexity and imprecision. Like many other stuck-at based techniques, MMA has the disadvantage of intractable diagnosis size. In addition, the MMA technique was originally demonstrated only on circuits smaller than nearly every circuit in the ISCAS-85 benchmark suite. The MMA technique also disregards bridge resistance, variable downstream logic thresholds, and the possibility of state-holding bridging fault behavior. These simplifying assumptions, however, enabled an approach to diagnosing bridging faults using relatively simple stuck-at information, a desirable feature considering the expense of realistic fault models.
Despite its shortcomings, however, the MMA technique has many advantages, the most notable of which are the use of the ubiquitous single stuck-at fault model, obviation of the need for additional circuit information for bridging fault diagnosis, and a small likelihood of misleading diagnoses under modeled conditions.
2.5.1 MMA Theory
When MMA was first introduced, it used what is referred to as the voting model to describe bridging fault behavior. The MMA diagnostic theory, described below, followed from some relatively simple observations about bridging fault behavior under the voting model.
Assume that a test vector v detects a bridging fault in a CMOS circuit. A detected error necessarily indicates that the two bridged nodes have opposite fault-free logic values for this vector. The driving transistor networks of these two nodes will each attempt to assert competing logic values on the bridge; the resulting bridge voltage is determined by the drive strengths, or conductances, of the competing networks. In the voting model, the stronger network wins this competition, or vote, and asserts its logic value on the bridged nodes.
The application of v causes one node to outvote the other, driving the outvoted node to a faulty logic value. The key observation of the MMA technique is that since v is able to sensitize the outvoted node and propagate the faulty value to a circuit output, it must also detect the stuck-at fault for the outvoted node stuck at the faulty value. Therefore, v must appear in a complete list of detecting vectors for this stuck-at fault on the outvoted node.
This complete list of the detecting vectors for a particular fault is contained in its fault signature. The basis of the MMA technique is the construction and use of composite signatures for each potential bridging fault. The composite signature of a bridging fault is the union of the four associated single stuck-at signatures. As shown in FIG. 1, the MMA composite signature for node X bridged to node Y is the union of the four stuck-at signatures for the two bridged nodes, where each stuck-at signature is a set of output:vector pairs. By the reasoning given above, MMA concludes that the fault signature of a bridging fault will be contained in, or will be a subset of, the bridging fault""s composite signature.
The process of diagnosis can be outlined with the use of a few definitions. First, let v and o represent vector and output (single output pin) variables, respectively. Then, let v represent a logical value: v(o, v) is the logical value at output o upon application of vector v in the fault-free circuit; and vf (o, v) is logical value at output o upon application of vector v in the presence of fault f.
The observed faulty behavior is represented by Bf, the set of error-carrying  less than output:vector greater than  pairs:
Bf={∀ less than o:v greater than |v(o, v)xe2x89xa0vf(o, v)}.xe2x80x83xe2x80x83(1)
In the rest of this description, the subscript f will be dropped from B, since it is understood that B will refer to a single faulty behavior.
The MMA technique builds a composite signature, denoted here by Cf, for every possible node pair in the circuit, from four stuck-at signatures, denoted by Sf. In this notation, SX0 refers to the stuck-at signature for node X stuck-at 0, and CX@Y refers to the composite signature for node X bridged to node Y. Duplicates entries in Cf are dropped after concatenation.
SX0={∀ less than o:v greater than |v(o, v)xe2x89xa0vX0(o, v)}xe2x80x83xe2x80x83(2)
CX@Y=SX0∪SX1∪SY0∪SY1xe2x80x83xe2x80x83(3)
The MMA diagnostic algorithm compares each composite signature with the observed behavior; a composite signature containing entries that are a superset of the entries contained in the observed faulty behavior is said to be a match. Note that since o represents a single output pin, there is an entry representing every error-carrying output pin for every vector in Sf, Cf, and Bf. Therefore, the subset matching criteria applies to outputs as well as vectors.
The MMA diagnosis of a bridging fault is a list of candidate bridging faults having composite signatures that match the observed faulty behavior. A diagnosis can be formalized as
D={∀Ci|BCi},xe2x80x83xe2x80x83(4)
where the subscript i indicates an index through all (composite signature) candidates. Note that this technique does not require explicit simulation of bridging faults, only stuck-at fault simulation to create stuck-at signatures.
All of the previously-described operations, including composite signature construction and candidate matching, are demonstrated in Table 1 and Table 2. Table 1 gives a stuck-at fault dictionary, or list of all stuck-at faults and their signatures, for a trivial circuit of only three nodes and a single output. The nodes are labeled A, B, and C; the output is unnamed and for simplicity is omitted from the signatures. Table 2 shows the resulting MMA composite bridging fault dictionary, with composite signatures constructed as described previously.
The two diagnosis examples of Table 1 and Table 2, while trivial, demonstrate both the relative simplicity and the imprecision characteristic of the MMA technique. The first observed behavior, {1, 2, 4}, is a subset of all three composite signature candidates; that, it matches all bridging faults and, therefore, the diagnosis therefore implicates every node pair in the circuit. The second observed behavior {2, 3} is also poorly distinguished, as it matches with two of the three candidates; faults (B@C) and (C@A). Note that while the bridging fault diagnoses are imprecise, all six stuck-at faults are uniquely identified by their stuck-at signatures; this resolution is lost, however, in the construction of the composite signatures.
2.5.2 Evaluating Diagnoses
As defined above, a match is a subset relation between the observed faulty behavior and a composite signature. If the identity of the actual fault is known, an individual match can be evaluated for correctness: does a matching composite signature identify, completely or partially, the nodes involved in the actual bridging fault? Extending from this, the quality of a diagnosis can be evaluated as the quality of its component composite signature, or fault candidate, matches.
For this purpose, a bridging fault is assumed to involve exactly two nodes; all matching composite signatures similarly correspond to bridging fault candidates made up of two nodes. There are then three types of matches defined in MMA: A correct match correctly identifies both of the nodes involved in the bridge, a partial match correctly identifies only one of the nodes involved in the bridge, and a misleading match identifies neither of the nodes involved in the bridge. An example bridging fault and examples of each type of corresponding match are given in Table 3.
Having defined the types of matches, in MMA terminology the quality of a diagnosis is indicated in one of three ways, based on the matches used to construct it. An exact diagnosis contains only the correct match, a partial diagnosis contains the correct match in addition to other matches, and an incorrect diagnosis does not contain the correct match. Incorrect diagnoses can be further divided into three categories as shown in Table 4. An incomplete diagnosis contains partial matches but not the correct match, a misleading diagnosis contains only misleading matches, and a failed diagnosis is empty. (All diagnosis types except incomplete, introduced for purposes of the present invention, are defined in MMA). Incomplete, misleading, and failed diagnoses are all considered incorrect diagnoses, as they do not contain the correct match. Although all types of incorrect diagnoses are undesirable, it is much better to have a failed diagnosis than a misleading diagnosis; a failed diagnosis is clearly incorrect and cannot mislead the search for a defect.
If a bridging fault can create a feedback loop in the circuit, some test vectors may cause circuit outputs to oscillate. Such a vector is said to only possibly detect (or potentially detect) the bridging fault. Under the assumptions made in the definition of MMA, namely, for two bridged nodes, with one node outvoted and error-carrying for any detecting vector, zero-resistance bridges, and the bridge voltage being a definite logic value with regard to downstream gates, the inclusion of possibly detecting test vectors can lead to misleading and failed diagnoses; but if the possibly detecting vectors are ignored, misleading and failed diagnoses will not occur, and the correct fault will always be part of the diagnosis. This is stated as a theorem in MMA:
When possibly detecting patterns are ignored, the fault signature of a bridging fault must be contained in its composite signature.
The MMA theorem guarantees that incorrect diagnoses will not occur, but it places no bound on the size of the diagnosis. A diagnosis with many misleading or partial matches is undesirable; it can result in the investigation of portions of the chip not involved in the fault. This is potentially frustrating, because physical investigation of the failed part sometimes requires destruction of the layers above the site of the suspected defect. Once these layers are gone, nearby suspected sites cannot be investigated. The size of the average diagnosis using the MMA technique on the ISCAS-85 benchmark circuits is at least 33 matches (for the C880) and can reach over 200 matches (for the C7552).
The MMA theorem guarantees that the correct match will appear in the diagnosisxe2x80x94as long as the observed behavior of the fault is not affected by variable logic thresholds, which commonly affect the behavior of faulty CMOS circuits.
2.5.3 Byzantine Generals Problem
In order to be detected with a logic test, a bridging fault must create an error that is propagated to one or more circuit outputs. At the fault site, this error is a voltage that is subject to interpretation as different logic values by downstream logic gates. Because gate input logic thresholds are not identical, different downstream gates can interpret the voltage as different logic values: this phenomenon is known as the Byzantine Generals Problem for bridging faults. FIG. 2 shows a simple example of voltage interpretation in the presence of variable logic thresholds. Node B has an intermediate ( faulty) voltage value due to the presence of a bridge. Each gate interprets the voltage as a different logic value.
This behavior has important implications for diagnosis: the propagation conditions for the error induced by a bridging fault are not necessarily the same as those caused by a stuck-at fault. Therefore, a detecting test vector may or may not display the same behavior at the circuit outputs for a bridging fault as for a stuck-at fault on one of the bridged nodes. Note that the faulty voltage on node B in FIG. 2 will not cause the circuit to appear, for the node values shown, as if B were stuck-at 1 or stuck-at 0; each circuit output reports evidence that there is a different value on node B.
The Byzantine Generals Problem can affect diagnosis in several ways. It might cause the error introduced by the bridging fault to be propagated to more or fewer circuit outputs than would be affected by a single stuck-at fault. Alternatively, the error introduced by the bridging fault may be detected by a vector, or propagated to an output, that would never evince an error for any one of the four single stuck-at faults. The Byzantine Generals Problem may also cause errors to occur downstream from both of the bridged nodes at the same time. Each of these is an example of how variable logic thresholds nullify the previously-stated MMA theorem and cause incorrect diagnoses to result for real circuits.
2.6 Candidate Space Problems
The purpose of fault diagnosis in electronic circuits, and particularly in integrated circuits, is to identify the location of a fault so that the cause of the fault can be categorized. This is necessary for several steps in the manufacturing process: the initial system debug, the ramp to volume production, the yield improvement phase, and volume manufacturing testing. As IC manufacturing technology becomes more complex and feature sizes continue to shrink, the manual search and categorization of defects is becoming exceedingly expensive and time-consuming. The expense of a manual search makes it crucial for automated diagnosis tools to pinpoint the location of a defect to only a few locations.
As a result, two general approaches to this candidate-space problem have been previously developed.
The first conventional approach assumes that all   "AutoLeftMatch"      (                            n                                      2                      )  
possible bridging faults for a circuit need to be considered. However, building an   "AutoLeftMatch"      (                            n                                      2                      )  
-sized fault dictionary is prohibitively expensive, so this line of research has focused on algorithms that continuously eliminate large portions of the candidate space based on the observed fault signature (without building a dictionary). Once a bridging fault is removed from the candidate space it is no longer considered. A major weakness of this approach is that if the bridging fault""s behavior is not well-characterized, it is likely to be removed from the diagnosis. A major strength is that the physical design of the circuit is not necessary for diagnosing potential bridging faults.
The second conventional approach uses the physical design of the circuit to eliminate bridging faults between lines that are extremely unlikely to be shorted together due to the physical location of the nodes comprising the bridging fault. If the two nodes are never closer than some minimum distance, or if there is another node separating them that would also be involved in the bridge, then that bridging fault is not considered. Errors in understanding and predicting the bridging fault behavior are tolerated by finding the best match to the observed signature. However, at times information about the physical design of the circuit is proprietary, the degree of information stored about a circuit changes over its lifecycle, or the number of nodes is simply too large to explicitly consider all pairs.
Most commercial automated diagnosis tools rely on the xe2x80x9cstuck-atxe2x80x9d fault model as a basis for fault diagnosis. However, it has been shown repeatedly that the stuck-at fault model does not accurately reflect the behavior of current-generation silicon defects. While a more realistic fault model provides better diagnoses, a bridging fault diagnosis algorithm that uses the stuck-at fault model as a foundation would not require a sacrifice of performance or a change in existing design flows. Therefore, there is a also a need for a method of diagnosing bridging faults that uses the stuck-at model and which, if necessary, can be utilized without having specific physical information about the circuit.
The present invention comprises a method for fault diagnosis of electronic circuits and, in particular, a method for diagnosing bridging faults with stuck-at signatures, with several important changes to the conventional MMA technique. By way of example, and not of limitation, only those faults determined to be realistic through inductive fault analysis are considered as candidates. The number of realistic faults is much smaller than the number of all theoretically possible bridges, not only improving the precision of the diagnoses, but making the technique feasible for much larger circuits. Second, match restrictions and match requirements are imposed during matching in order to minimize diagnosis size. Finally, match ranking is applied and the matching criteria relaxed to further increase the effective precision and to increase the number of correct diagnoses. Using all described improvements, the reported experiments show that at least 90% of the time the correct match is found in a diagnosis of size ten or less, a significant indication of diagnostic effectiveness.
Furthermore, it will be appreciated that the use of stuck-at fault information to perform bridging fault diagnosis is based on a somewhat simplified view of bridging fault behavior: in order for a bridging fault to be detected, the two bridged nodes must have opposite values in the fault-free circuit but, in the presence of the fault, both bridged nodes will have the same value (one of the two nodes will dominate). This means that any vector that detects a bridging fault will detect one of the four stuck-at faults associated with the two nodes. To avoid having to build a prohibitively expensive   "AutoLeftMatch"      (                            n                                      2                      )  
-sized fault dictionary, the present invention further comprises two alternative embodiments of a method to reduce the candidate space involved in bridging fault diagnosis without the aid of physical design information. The first embodiment uses the intuitive idea of an initial stuck-at fault diagnosis to attempt to identify one of the bridged nodes. The second embodiment technique identifies all candidates that can have an arbitrary intersection threshold with the behavior, providing an optimal diagnosis under our scoring criteria. Both embodiments only consider and construct O(n) candidates, about as many as previously reported when using realistic fault lists. Either embodiment can be used to minimize the construction of composite signatures even when beginning with a realistic fault list.
An object of the invention is to provide a fast, accurate and computationally non-complex method for precise diagnosis of bridging faults.
Another object of the invention is to reduce the size of the fault dictionary required for bridging fault diagnosis.
Another object of the invention is to improve the conventional MMA technique for bridging fault diagnosis.
Another object of the invention is to diagnose bridging faults in absence of physical information regarding a circuit.
Further objects and advantages of the invention will be brought out in the following portions of the specification, wherein the detailed description is for the purpose of fully disclosing preferred embodiments of the invention without placing limitations thereon.